Successive over-relaxation について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Successive over-relaxation ：ウィキペディア英語版

Successive over-relaxation
In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process.
It was devised simultaneously by David M. Young, Jr. and by H. Frankel in 1950 for the purpose of automatically solving linear systems on digital computers. Over-relaxation methods had been used before the work of Young and Frankel. An example is the method of Lewis Fry Richardson, and the methods developed by R. V. Southwell. However, these methods were designed for computation by human calculators, and they required some expertise to ensure convergence to the solution which made them inapplicable for programming on digital computers. These aspects are discussed in the thesis of David M. Young, Jr.
==Formulation==
Given a square system of ''n'' linear equations with unknown x:
:

A\mathbf x = \mathbf b

where:
:

A=\begin a_ & a_ & \cdots & a_ \\ a_ & a_ & \cdots & a_ \\ \vdots & \vdots & \ddots & \vdots \\a_ & a_ & \cdots & a_ \end, \qquad  \mathbf = \begin x_ \\ x_2 \\ \vdots \\ x_n \end , \qquad  \mathbf = \begin b_ \\ b_2 \\ \vdots \\ b_n \end.

Then ''A'' can be decomposed into a diagonal component ''D'', and strictly lower and upper triangular components ''L'' and ''U'':
:

A=D+L+U,

where
:

D = \begin a_ & 0 & \cdots & 0 \\ 0 & a_ & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_ \end, \quad L = \begin 0 & 0 & \cdots & 0 \\ a_ & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_ & a_ & \cdots & 0 \end, \quad U = \begin 0 & a_ & \cdots & a_ \\ 0 & 0 & \cdots & a_ \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end.

The system of linear equations may be rewritten as:
:

) \mathbf

for a constant ''ω'' > 1, called the ''relaxation factor''.
The method of successive over-relaxation is an iterative technique that solves the left hand side of this expression for x, using previous value for x on the right hand side. Analytically, this may be written as:
:

) \mathbf^\big)=L_w \mathbf^+\mathbf,

where

\mathbf^

is the ''k''th approximation or iteration of

\mathbf

and

\mathbf^

is the next or ''k'' + 1 iteration of

\mathbf

.
However, by taking advantage of the triangular form of (''D''+''ωL''), the elements of x^(''k''+1) can be computed sequentially using forward substitution:
:

x^_i  = (1-\omega)x^_i + \frac a_x^_j - \sum_ a_x^_j \right),\quad i=1,2,\ldots,n.

The choice of relaxation factor ''ω'' is not necessarily easy, and depends upon the properties of the coefficient matrix. In 1947, Ostrowski proved that if

A

is symmetric and positive-definite then

\rho(L_\omega)<1

for

0<\omega<2

. Thus convergence of the iteration process follows, but we are generally interested in faster convergence rather than just convergence.

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Successive over-relaxation」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース